Butterfly switches and rings with bypasses are well-known (the schematic diagrams are shown in FIGS. 1A and 1B, respectively) and are described in a number of computer architecture textbooks.
A butterfly switch as shown in FIG. 1A allows communication between N sources and N destinations with delay on the order of logarithm of N. The delay does not depend on relative positions of source and destination; and the operation of the permutation devices (shown as boxes in FIG. 1A) is very simple, so a hardware implementation is cheap and efficient. An important characteristic of a butterfly switch is its linear scalability, i.e. an arbitrarily large switch can be built so the aggregate throughput of the switch grows linearly with the number of inputs or outputs. However, a failure of a single component of a butterfly switch causes significant degradation of end-to-end connectivity because every single permutation device and all corresponding links are present in multiple source-destination paths. Consequently, although they are simple and efficient, butterfly switches have found limited use because they lack fault tolerance.
A ring with bypasses is shown in FIG. 1B. A ring with bypasses has redundant links bypassing every element of the ring, so if an element has failed, the connectivity will still be preserved. A ring with bypasses can handle failures of arbitrary numbers of elements, as long as failed elements are not adjacent. Ring-based data interconnects, however, are not linearly scalable, i.e. they have aggregate throughput limited by the speed of a single connection.
FIG. 1C shows a wrapped butterfly switch, wherein the permutation devices in the first and the last rows of a butterfly switch are merged. Like the original butterfly switch, the wrapped butterfly switch is not fault-tolerant.
Other interconnect topologies comparable to butterfly switches in terms of linear scalability include hypercubes (shown in FIG. 1D), fat trees (shown in FIG. 1E), and multibutterflies (as described in U.S. Pat. No. 5,521,591 to Arora et al. (1996).
Hypercubes are fault-tolerant in most cases, but require relatively complicated routing algorithms and multi-port switching elements which limit the size of a switch by the design limitations of the switching elements. Existing commercial implementations of hypercube switches (such as by nCUBE Corp., Beaverton, Oreg.) are relatively slow and do not support parallel data ports due to the prohibitively large number of pins required. Moreover, routing through a hypercube does not yield consistent latency due to its different path lengths.
Fat trees are generally comparable to hypercubes in terms of complexity and fault tolerance.
A detailed description and discussion of the aforementioned interconnect topologies can be found in Introduction To Parallel Algorithms And Architectures: Arrays, Trees, Hypercubes by F. Thomson Leighton, Morgan Kaufmann Publishers, 1992.
There are numerous works of prior art augmenting the aforementioned basic data interconnect technologies to improve fault tolerance or performance by replicating basic switching networks or adding redundant links and switching equipment. The common drawback of all those works is that they increase complexity even more, thus making very high speed implementations expensive or impossible. Those works include: U.S. Pat. No. 5,521,591 to Arora et al. (1996) describing a multibutterfly-based data interconnect; U.S. Pat. No. 4,968,977 to Chinnaswamy et al. (1990) and U.S. Pat. No. 4,651,318 to Luderer (1987) describing non-linearly scalable modular crossbar data interconnects; U.S. Pat. No. 5,471,623 to Napolitano (1995) describing a bi-directional packet switch; and a number of relevant works related to connection-oriented data networks, U.S. Pat. No. 5,040,173 to Richards (1991), U.S. Pat. No. 4,875,736 to Posner and Smyth (1989) and U.S. Pat. No. 5,542,048 to Olnowich et al. (1996).